//普通二叉树遍历：空间复杂度O（N）
//Morris二叉树遍历：空间复杂度O（1）
public class TreeMorrisSearch {
}
class MorrisSearchSolution{
    void morrisPre(TreeNode root){
        if(root==null)return;
        TreeNode cur = root;
        TreeNode mostRight = null;
        while(cur!=null){
            mostRight =  cur.left;
            if(mostRight!=null){//当前节点cur有左子树
                //找到左子树上最右节点
                while(mostRight.right!=null&&mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right==null){//首次到达mostRight
                    mostRight.right = cur;//mostRight右指向cur
                    System.out.print(cur.val+" ");//重复到达节点只在首次到达时打印
                    cur = cur.left;//cur左移动
                    continue;
                }else{
                    mostRight.right = null;//非首次到达，恢复mostRight右指向null
                }
            }else System.out.print(cur.val+" ");//没有左子树，只经过一次，直接打印
            cur = cur.right;//cur没有左子树，或者cur左子树上最右节点的右指针指向cur，cur向右移动
        }
    }
}
